package org.xteam.sled.tree;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.xteam.sled.decoder.DecoderBuilder.Match;
import org.xteam.sled.decoder.DecoderBuilder.recognized_constructor;
import org.xteam.sled.matcher.Arm;
import org.xteam.sled.model.AbsoluteDisjunct;
import org.xteam.sled.model.AbsoluteField;
import org.xteam.sled.model.AbsolutePattern;
import org.xteam.sled.model.AbsoluteSequence;
import org.xteam.sled.model.RangeConstraint;
import org.xteam.sled.semantic.GlobalState;
import org.xteam.sled.semantic.Range;
import org.xteam.sled.semantic.exp.Exp;
import org.xteam.sled.semantic.exp.FalseHood;
import org.xteam.sled.semantic.exp.Tautology;

public class TreeBuilder {

	private static Heuristic[] Heuristics = new Heuristic[] {
			new LeafArmHeuristic(),
			new ChildArmHeuristic(),
			new NoMatchHeuristic(),
			new ChildDisjunctsHeuristic(),
			new BranchFactorHeuristic() };

	public Tree mkTree(Match<recognized_constructor> match) {
		return tree(0, match.getArms());
	}

	private Tree tree(int depth, List<Arm> arms) {
		if (needsSplitting(arms))
			return split(depth, arms);
		return noSplit(arms);
	}

	protected boolean needsSplitting(List<Arm> arms) {
		if (arms.isEmpty())
			return false;
		AbsolutePattern pat = arms.get(0).getPattern();
		if (!alwaysSatisfied(arms.get(0).getConditions()))
			return hasConstraint(arms);

		String pname = pat.name();
		List<AbsoluteDisjunct> ds = pat.getDisjuncts();

		String name = ds.isEmpty() || ds.get(0).name() == null ? pname : ds
				.get(0).name();

		for (AbsoluteDisjunct d : ds) {
			String disname = d.name();
			if (disname == null)
				disname = pname;
			if (!disname.equals(name))
				return true;
			else if (AlwaysMatches_dis(d))
				return false;
		}
		return true;
	}

	private boolean AlwaysMatches_arm(Arm arm) {
		return alwaysSatisfied(arm.getConditions())
				&& AlwaysMatches_pat(arm.getPattern());
	}

	private boolean AlwaysMatches_pat(AbsolutePattern pattern) {
		for (AbsoluteDisjunct ds : pattern.getDisjuncts()) {
			if (AlwaysMatches_dis(ds)) {
				return true;
			}
		}
		return false;
	}

	private boolean AlwaysMatches_dis(AbsoluteDisjunct d) {
		if (d.getSequence().getConstraints().isEmpty())
			return alwaysSatisfied(d.getConditions());
		return false;
	}

	private boolean alwaysSatisfied(Collection<Exp> conditions) {
		for (Exp cond : conditions) {
			if (!new Tautology().test(cond)) {
				return false;
			}
		}
		return true;
	}
	
	private boolean neverSatisfied(List<Exp> conditions) {
		for (Exp cond : conditions) {
			if (new FalseHood().test(cond)) {
				return true;
			}
		}
		return false;
	}

	private static boolean hasConstraint(List<Arm> arms) {
		for (Arm arm : arms) {
			for (AbsoluteDisjunct d : arm.getPattern().getDisjuncts()) {
				if (d.getSequence().getConstraints().size() > 0)
					return true;
			}
		}
		return false;
	}

	private Tree split(int depth, List<Arm> arms) {
		List<AbsoluteField> afields = mentions(arms);
		afields = GlobalState.Match.strategy.limitFields(afields);
		Map<AbsoluteField, List<SplitResult>> candidates = new HashMap<AbsoluteField, List<SplitResult>>();
		for (AbsoluteField f : afields) {
			candidates.put(f, splitAt(f, arms));
		}
		for (Heuristic h : Heuristics) {
			if (afields.size() == 1)
				break;
			afields = findMaxima(h, candidates, afields);
		}
		List<Edge> edges = new ArrayList<Edge>();
		for (SplitResult res : candidates.get(afields.get(0))) {
			edges.add(new Edge(res.range, tree(depth + 1, res.arms)));
		}
		return new TreeNode(afields.get(0), edges);
	}

	private Tree noSplit(List<Arm> arms) {
		arms = trimImpossibleArms(arms);
		String name = arms.isEmpty() ? null : getNodename(arms);
		if (name != null && GlobalState.lowerPatternNames)
			name = name.toLowerCase();
		return new LeafNode(arms, name);
	}

	private String getNodename(List<Arm> arms) {
		String nodeName = null;
		for (Arm arm : arms) {
			String armName = null;
			if (arm.name() != null) {
				armName = arm.getPattern().name();
				if (arm.getPattern().getDisjuncts().size() > 0) {
					String name = arm.getPattern().getDisjuncts().get(0).name();
					if (name != null)
						armName = name;
				}
			}
			if (armName != null) {
				if (nodeName == null)
					nodeName = armName;
				else if (!nodeName.equals(armName)) {
					System.err.println("ambiguous name for matching arm "
							+ nodeName + "/" + armName);
					nodeName = null;
				}
			}
		}
		return nodeName;
	}

	private List<Arm> trimImpossibleArms(List<Arm> arms) {
		List<Arm> res = new ArrayList<Arm>();
		for (Arm arm : arms) {
			if (alwaysSatisfied(arm.getConditions())) {
				res.clear();
				res.add(arm);
				return res;
			} else if (!neverSatisfied(arm.getConditions())) {
				res.add(arm);
			}
		}
		return res;
	}
	
	private List<AbsoluteField> findMaxima(Heuristic hfun,
			Map<AbsoluteField, List<SplitResult>> candidates,
			List<AbsoluteField> afields) {
		Integer max = null;
		List<AbsoluteField> bestFields = new ArrayList<AbsoluteField>();
		for (AbsoluteField f : afields) {
			int score = hfun.run(this, candidates.get(f), f);
			if (max == null || score > max) {
				max = score;
				bestFields.clear();
				bestFields.add(f);
			} else if (score == max) {
				bestFields.add(f);
			}
		}
		return bestFields;
	}

	private List<SplitResult> splitAt(AbsoluteField f, List<Arm> arms) {
		Set<Integer> cutSet = new HashSet<Integer>();
		cutSet.add(0);
		cutSet.add(f.field().fieldmax());
		for (Arm arm : arms) {
			for (AbsoluteDisjunct ds : arm.getPattern().getDisjuncts()) {
				for (RangeConstraint<AbsoluteField> rc : ds.getSequence()
						.getConstraints()) {
					if (rc.field().equals(f)) {
						cutSet.add(rc.low());
						cutSet.add(rc.high());
					}
				}
			}
		}
		List<Integer> cuts = new ArrayList<Integer>(cutSet);
		Collections.sort(cuts);
		List<SplitResult> res = new ArrayList<SplitResult>();
		for (int i = 0; i < cuts.size(); ++i) {
			if (i < (cuts.size() - 1)) {
				int lo = cuts.get(i);
				int hi = cuts.get(i + 1);
				res.add(new SplitResult(new Range(lo, hi), applyConstraint(f,
						lo, hi, arms)));
			}
		}
		return res;
	}

	private List<Arm> applyConstraint(AbsoluteField f, int lo, int hi,
			List<Arm> arms) {
		List<Arm> res = new ArrayList<Arm>();
		for (Arm arm : arms) {
			AbsolutePattern np = pmatch(arm.getPattern(), f, lo, hi);
			if (np != null) {
				res.add(new Arm(np, arm.getAnswers(), arm.getConditions()));
			}
		}
		if (res.size() > 0 && AlwaysMatches_arm(res.get(0))) {
			Arm a = res.get(0);
			res.clear();
			res.add(a);
		}
		return res;
	}

	private AbsolutePattern pmatch(AbsolutePattern pattern, AbsoluteField f,
			int lo, int hi) {

		List<AbsoluteDisjunct> res = new ArrayList<AbsoluteDisjunct>();
		for (AbsoluteDisjunct d : pattern.getDisjuncts()) {
			List<RangeConstraint<AbsoluteField>> cs = new ArrayList<RangeConstraint<AbsoluteField>>();
			for (RangeConstraint<AbsoluteField> c : d.getSequence()
					.getConstraints()) {
				if (!c.field().equals(f)) {
					cs.add(c);
				} else if (c.low() > lo || hi > c.high()) {
					if (c.high() > lo && hi > c.low())
						throw new RuntimeException("bad interval");
					cs = null;
					break;
				}
			}
			if (cs != null) {
				res.add(new AbsoluteDisjunct(d.name(), d.getConditions(),
						new AbsoluteSequence(cs, d.getSequence().getLabels(), d
								.getSequence().bitLength())));
			}
		}
		if (res.isEmpty())
			return null;
		return new AbsolutePattern(pattern.name(), res);
	}

	protected static class SplitResult {

		Range range;
		List<Arm> arms;

		public SplitResult(Range range, List<Arm> arms) {
			this.range = range;
			this.arms = arms;
		}

	}

	private List<AbsoluteField> mentions(List<Arm> arms) {
		Set<AbsoluteField> res = new HashSet<AbsoluteField>();
		for (Arm arm : arms) {
			for (AbsoluteDisjunct ds : arm.getPattern().getDisjuncts()) {
				for (RangeConstraint<AbsoluteField> cnst : ds.getSequence()
						.getConstraints()) {
					res.add(cnst.field());
				}
			}
		}
		return new ArrayList<AbsoluteField>(res);
	}

}
